home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / prog / graph / shorttest.c < prev    next >
C/C++ Source or Header  |  1994-08-05  |  7KB  |  352 lines
  1. #include <LEDA/stream.h>
  2. #include <LEDA/ugraph.h>
  3. #include <LEDA/node_pq.h>
  4. #include <LEDA/b_node_pq.h>
  5.  
  6. int  dijkstra1(UGRAPH<int,int>& g, node source, node target) 
  7. {
  8.   // use a linear list priority queue  (node_list)
  9.   // and node_data<int> for dist values
  10.  
  11.   node_data<int> dist(g,MAXINT); // initialize labels
  12.   node_list      labeled;        // candidate nodes
  13.   node v;
  14.  
  15.   dist[source] = 0;
  16.  
  17.   labeled.push(source);
  18.  
  19.   while ( ! labeled.empty() )
  20.   {
  21.     // find node v with minimal dist[v] by linear search
  22.  
  23.     v = labeled.first();
  24.     int dv = dist[v];
  25.     node u = labeled.succ(v);
  26.     while (u)
  27.     { if (dist[u] < dv)  { v = u; dv = dist[v]; }
  28.        u = labeled.succ(u);
  29.      }
  30.       
  31.  
  32.     if (v == target) break;
  33.  
  34.     edge e;
  35.  
  36.     forall_adj_edges(e,v) 
  37.     { node w = g.opposite(v,e);
  38.       int  d = dist[v] + g.inf(e);
  39.       if (dist[w] > d) 
  40.       { if (dist[w] == MAXINT) labeled.append(w); // first time touched
  41.     dist[w] = d;
  42.        }
  43.       }
  44.  
  45.     labeled.del(v);
  46.   } 
  47.  
  48.   return dist[v];
  49. }
  50.  
  51. int  dijkstra2(UGRAPH<int,int>& g, node source, node target) 
  52. {
  53.   // use a node priority queue (node_pq)
  54.   // and node_data<int> for dist values
  55.  
  56.   node_data<int> dist(g,MAXINT); // initialize labels
  57.   dist[source] = 0;
  58.  
  59.   node_pq<int> PQ(g);             // candidate nodes
  60.   PQ.insert(source,0);
  61.  
  62.   while (! PQ.empty())
  63.   { 
  64.     node v = PQ.del_min();
  65.     int dv = dist[v];
  66.  
  67.     if (v == target) break;
  68.  
  69.     edge e;
  70.     forall_adj_edges(e,v)
  71.     { node w = g.opposite(v,e);
  72.       int d = dv + g.inf(e);
  73.       if (d < dist[w]) 
  74.       { if (dist[w] == MAXINT)
  75.            PQ.insert(w,d);
  76.         else
  77.            PQ.decrease_inf(w,d);
  78.         dist[w] = d;
  79.        }
  80.     }
  81.  
  82.   }
  83.  
  84.   return dist[target];
  85. }
  86.  
  87.  
  88.  
  89.  
  90. int dijkstra3(UGRAPH<int,int>& g, node s, node t) 
  91. {
  92.   // use a bounded node priority queue (b_node_pq)
  93.   // and a node_array<int> for dist values
  94.  
  95.   node_array<int> dist(g,MAXINT);
  96.  
  97.   b_node_pq<101> PQ(t);  // on empty queue del_min returns t 
  98.  
  99.   dist[s] = 0;
  100.  
  101.   for (node v = s;  v != t; v = PQ.del_min() )
  102.   { 
  103.     int dv = dist[v];
  104.  
  105.     edge e;
  106.     forall_adj_edges(e,v) 
  107.     { node w = g.opposite(v,e);
  108.       int d = dv + g.inf(e);
  109.       if (d < dist[w])
  110.       { if (dist[w] != MAXINT) PQ.del(w);
  111.     dist[w] = d;
  112.         PQ.insert(w,d);
  113.        }
  114.      }
  115.    }
  116.  
  117.   return dist[t];
  118. }
  119.  
  120.  
  121. int dijkstra4(UGRAPH<int,int>& g, node s, node t) 
  122. {
  123.   // use a bounded node priority queue (b_node_pq)
  124.   // and node_data<int> for dist values
  125.  
  126.   node_data<int> dist(g,MAXINT);
  127.  
  128.   b_node_pq<101> PQ(t);  // on empty queue del_min returns t 
  129.  
  130.   dist.set(s,0);
  131.  
  132.   for (node v = s;  v != t; v = PQ.del_min() )
  133.   { 
  134.     int dv = dist(v);
  135.  
  136.     edge e;
  137.     forall_adj_edges(e,v) 
  138.     { node w = g.opposite(v,e);
  139.       int d = dv + g.int_inf(e);
  140.       if (d < dist(w))
  141.       { if (dist(w) != MAXINT) PQ.del(w);
  142.     dist.set(w,d);
  143.         PQ.insert(w,d);
  144.        }
  145.      }
  146.    }
  147.  
  148.   return dist(t);
  149. }
  150.  
  151.  
  152. int  moore1(UGRAPH<int,int>& g, node source, node target)
  153. {
  154.   // use a queue of candidate nodes (node_list)
  155.   // and node_data<int> for dist values
  156.  
  157.   node_data<int> dist(g,MAXINT);   // initialize labels
  158.   dist[source] = 0;
  159.  
  160.   node_list labeled;               // queue of candidate nodes
  161.   labeled.append(source);
  162.  
  163.   while (! labeled.empty()) 
  164.   { node v = labeled.pop();
  165.     int dv = dist[v];
  166.  
  167.     if (dv >= dist[target]) continue;
  168.  
  169.     edge e;
  170.     forall_adj_edges(e,v) 
  171.     { node w = g.opposite(v,e);
  172.       int d = dv + g.inf(e);
  173.       if (d < dist[w]) 
  174.       { if (!labeled(w)) labeled.append(w);
  175.     dist[w] = d;
  176.        }
  177.      }
  178.  
  179.    }
  180.  
  181.   return dist[target];
  182.  
  183. }
  184.  
  185.  
  186. int  moore2(UGRAPH<int,int>& g, node source, node target) 
  187. {
  188.   // use a double ended queue of candidate nodes (node_list)
  189.   // and a node_array<int> for dist values
  190.  
  191.   node_array<int> dist(g,MAXINT); // initialize labels
  192.   dist[source] = 0;
  193.  
  194.   node_list labeled;             // deque of candidate nodes
  195.   labeled.append(source);
  196.  
  197.   while (! labeled.empty()) 
  198.   { 
  199.     node v = labeled.pop();
  200.     int dv = dist[v];
  201.  
  202.     if (dv > dist[target]) continue;
  203.  
  204.     edge e;
  205.     forall_adj_edges(e,v)
  206.     { node w = g.opposite(v,e);
  207.       int  d = dv + g.inf(e);
  208.       if (d < dist[w]) 
  209.       { if ( ! labeled(w) ) 
  210.         { if (dist[w] == MAXINT)
  211.            labeled.append(w);
  212.         else
  213.            labeled.push(w);
  214.        }
  215.       dist[w] = d;
  216.        }
  217.      }
  218.  
  219.   }
  220.  
  221.   return dist[target];
  222. }
  223.  
  224.  
  225. int  moore3(UGRAPH<int,int>& g, node source, node target) 
  226. {
  227.   // use a double ended queue of candidate nodes (node_list)
  228.   // and node_data<int> for dist values
  229.  
  230.   node_data<int> dist(g,MAXINT); // initialize labels
  231.   dist.set(source,0);
  232.  
  233.   node_list labeled;             // deque of candidate nodes
  234.   labeled.append(source);
  235.  
  236.   while (! labeled.empty()) 
  237.   { 
  238.     node v = labeled.pop();
  239.     int dv = dist(v);
  240.  
  241.     if (dv > dist(target)) continue;
  242.  
  243.     edge e;
  244.  
  245.     forall_adj_edges(e,v)
  246.     { node w = g.opposite(v,e);
  247.       int  d = dv + g.int_inf(e);
  248.       if (d < dist(w)) 
  249.       { if ( ! labeled(w) ) 
  250.         { if (dist(w) == MAXINT)
  251.            labeled.append(w);
  252.         else
  253.            labeled.push(w);
  254.        }
  255.       dist.set(w,d);
  256.        }
  257.      }
  258.  
  259.   }
  260.  
  261.   return dist(target);
  262. }
  263.  
  264.  
  265.  
  266.  
  267. int main (int argc, char** argv) 
  268. {
  269.   UGRAPH<int,int>   g;
  270.  
  271.   int sourcename;
  272.   int targetname;
  273.   int len;
  274.  
  275.   string filename = "grid100";
  276.  
  277.   if (argc > 1) filename = argv[1];
  278.  
  279.   // read names of source and target from file <filename>
  280.  
  281.   file_istream  infile (filename);
  282.  
  283.   if ( ! (infile >> sourcename >> targetname) )
  284.   { cerr << "Cannot read file " << filename << endl;
  285.     exit(1);
  286.    }
  287.  
  288.   cout << "Source node: " << sourcename << endl;
  289.   cout << "Target node: " << targetname << endl;
  290.   newline;
  291.  
  292.   // read graph from file <filename>.graph
  293.  
  294.   float t0 = used_time();
  295.  
  296.   if (g.read(filename + ".graph") != 0)
  297.   { cerr << "Cannot read graph from file " << filename << ".graph" << endl;
  298.     exit(1);
  299.    }
  300.  
  301.   cout << string("Time for reading:  %5.2f",used_time(t0)) << endl;
  302.   newline;
  303.  
  304.  
  305.   // search for source and target nodes
  306.  
  307.   node source = nil;
  308.   node target = nil;
  309.  
  310.   node v;
  311.   forall_nodes(v,g) 
  312.   { if (g.inf(v) == sourcename) source = v;
  313.     if (g.inf(v) == targetname) target = v;
  314.    }
  315.  
  316.  
  317.  
  318.   t0 = used_time();
  319.  
  320.   if (g.number_of_edges() < 20000)
  321.   { len = dijkstra1(g, source, target);
  322.     cout <<string("Time for dijkstra1: %5.3f pathlength: %d",used_time(t0),len);
  323.     newline;
  324.    }
  325.   
  326.   len = dijkstra2(g, source, target);
  327.   cout <<string("Time for dijkstra2: %5.3f pathlength: %d",used_time(t0),len);
  328.   newline;
  329.   
  330.   len = dijkstra3(g, source, target);
  331.   cout <<string("Time for dijkstra3: %5.3f pathlength: %d",used_time(t0),len);
  332.   newline;
  333.  
  334.   len = dijkstra4(g, source, target);
  335.   cout <<string("Time for dijkstra4: %5.3f pathlength: %d",used_time(t0),len);
  336.   newline;
  337.   
  338.   len = moore1(g, source, target);
  339.   cout <<string("Time for moore1:    %5.3f pathlength: %d",used_time(t0),len);
  340.   newline;
  341.   
  342.   len = moore2(g, source, target);
  343.   cout <<string("Time for moore2:    %5.3f pathlength: %d",used_time(t0),len);
  344.   newline;
  345.  
  346.   len = moore3(g, source, target);
  347.   cout <<string("Time for moore3:    %5.3f pathlength: %d",used_time(t0),len);
  348.   newline;
  349.  
  350.   return 0;
  351. }
  352.